<?php
// https://mp.weixin.qq.com/s/ux6VSWAPwgOS32xlScr2kQ
class Solution {
    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        $res = '';
        $str_len = strlen($s);

        for ($i=0; $i<$str_len; $i++) {
            // 回文串的长度可能是奇数也可能是偶数 【i + 1处理偶数，i处理奇数】
            $s1 = $this->palindrome($s, $i, $i);
            $s2 = $this->palindrome($s, $i, $i+1);

            $res = strlen($res) < strlen($s1) ? $s1 : $res;
            $res = strlen($res) < strlen($s2) ? $s2 : $res;
        }

        return $res;
    }

    // 寻找回文串的问题核心思想是：从中间开始向两边扩散来判断回文串
    // 为什么要传入两个指针l和r呢？因为这样实现可以同时处理回文串长度为奇数和偶数的情况
    function palindrome($str, $l, $r) {
        $str_len = strlen($str);
        // 防止索引越界
        while ($l >= 0 && $r < $str_len && $str[$l] == $str[$r]) {
            // 向两边扩展
            $l--;
            $r++;
        }
        // 返回以l、为边界的回文串
        return substr($str, $l+1, $r- $l - 1);
    }
}

var_dump((new Solution())->longestPalindrome("babad"));
var_dump((new Solution())->longestPalindrome("aacxycaa"));
